package algorithm;

import java.util.Random;

/*
 给定数列A1,A2,...An，求最长递增子序列:
 在求以Ai为末元素的最长递增子序列时，找到所有在Ai前面且小于Ai的元素Aj，即j<i且Aj<Ai，如果这样的元素存在，
 那么对所有Aj,都有一个以Aj为末元素的最长递增子序列的长度S(j)，把其中最大的S(j)选出来，那么S(i)就等于最大的S(j)加上1，
 即以Ai为末元素的最长递增子序列，等于以使S(j)最大的那个Aj为末元素的递增子序列最末再加上Ai；
 如果这样的元素不存在，那么Ai自身构成一个长度为1的以Ai为末元素的递增子序列。
 阶段i:以第i个数为末元素
 状态S[i]:以第i个数为末元素的可能递增序列长度
 转移方程：S[i+1]=max{S[i]}+1
 */

/*
 * 动态规划查找最长递增子序列
 */
public class LCS {
	private static int maxSeqLength = 10;
	private int[] seq; // 序列数组
	private int[] status; // 状态数组：记录各个状态的最长递增子序列的长度

	public LCS() {
		this.initSeq();
		this.initStatus();
	}

	/*
	 * 核心算法
	 */
	public void dpFind() {
		for (int i = 1; i < this.seq.length; i++) {
			int subMaxLength = 0;
			for (int j = 0; j < i; j++) {
				if (this.seq[j] < this.seq[i]) {
					if (subMaxLength < this.status[j]) {
						subMaxLength = this.status[j];
					}
				}
			}
			this.status[i] = subMaxLength + 1;
		}

		System.out.print("序列最终状态：");
		this.printStatus();

		// 找状态数组中的最大值即为最长递增子序列
		int temp = 0;
		for (int i = 0; i < this.status.length; i++) {
			if (temp < this.status[i]) {
				temp = this.status[i];
			}
		}
		System.out.println("最长递增子序列长度:" + temp);
	}

	/*
	 * 初始化序列数组
	 */
	public void initSeq() {
//		Random random = new Random();
//		this.seq = new int[LCS.maxSeqLength];
//		for (int i = 0; i < seq.length; i++) {
//			this.seq[i] = random.nextInt(this.maxSeqLength);
//		}
		int[] nums = {5, 6, 4, 7};
		this.seq = nums;
	}

	/*
	 * 初始化序列最大值数组
	 */
	public void initStatus() {
		this.status = new int[LCS.maxSeqLength];
		for (int i = 0; i < status.length; i++) {
			if (i == 0) {
				this.status[i] = 1;
			} else {
				this.status[i] = 0;
			}
		}
	}

	/*
	 * 打印序列数组
	 */
	public void printSeq() {
		for (int i = 0; i < seq.length; i++) {
			System.out.print(seq[i] + "    ");
		}
		System.out.println();
	}

	/*
	 * 打印序列最大值数组
	 */
	public void printStatus() {
		for (int i = 0; i < status.length; i++) {
			System.out.print(status[i] + "    ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		LCS lcs = new LCS();
		System.out.print("测试序列          ：");
		lcs.printSeq();

		System.out.print("序列初始状态：");
		lcs.printStatus();

		lcs.dpFind();
	}
}
